package com.sourcetrip.my;


import com.sourcetrip.my.inter.functional.SelfBalancedTree;
import com.sourcetrip.my.modle.RedBlackNode;
import com.sourcetrip.my.modle.TreeNode;

/**
 * @author: ZhouBert
 * @date: 2020/12/18
 * @description: 红黑树 知识回顾：
 * 1.红黑树五大性质：
 * -1-所有的节点颜色：红色/黑色；
 * -2-Null 节点视为 黑色；
 * -3-根节点必须是 黑色；
 * -4-任意两个红色节点不能相连；
 * -5-任意节点到根节点的路径中，黑色节点的个数是一致的。
 * --
 * 这是个比较难的知识点，我要好好记笔记记下步骤：
 * 1.RedBlackNode
 * 2.afterAdd()
 * 3.afterRemove()
 * --
 */
public class RedBlackTree<E> extends BinarySearchTree<E> implements SelfBalancedTree<E> {

	/**
	 * 添加红黑树节点之后的修复
	 * 分析：
	 * 针对添加的情况进行讨论：
	 * 1.4 种添加到 Black 下：不处理；
	 * 2.
	 *
	 * @param node 添加的节点
	 */
	@Override
	protected void afterAdd(TreeNode<E> node) {
		if (node == null) {
			return;
		}
		//如果节点为 1，说明是根节点 -》 直接染色
//		if (size == 1)
//			setNodeBlack(node);
//			return;
//		}
		RedBlackNode<E> parentNode = getParentNode(node);
		if (parentNode == null) {
			//由于 上溢 时的递归，于是和 根节点染色进行合并
			setNodeBlack(node);
			return;
		}

		//1.如果挂在 Black Node 之下，直接返回
		if (isNodeBlack(parentNode)) {
			return;
		}
		//获取 uncle 节点(由于 parent.color == RED ,说明 必定存在 grand 节点！)
		RedBlackNode<E> uncleNode = getUncleNode(node);
		RedBlackNode<E> grandNode = getParentNode(parentNode);
		if (isNodeBlack(uncleNode)) {
			setNodeRed(grandNode);
			//2.parent.color == RED && uncle.color == BLACK (4)
			//可以从图得知，考虑 LL/RR/LR/RL 情况，
			// 并染色，根据上述四种不同的情况有不同的染色方式，最终都是：最高的节点为 BLACK，左右子节点为 RED
			if (parentNode.isLeftChild()) {
				//L
				if (node.isLeftChild()) {
					//LL-> black(p) + red(g)
					rotateRight(grandNode);

					//setNodeRed(grandNode);
					setNodeBlack(parentNode);
				} else {
					//LR-> black(node) + red(g)
					rotateLeft(parentNode);
					rotateRight(grandNode);

					setNodeBlack(node);
				}
			} else {
				//R
				if (node.isLeftChild()) {
					//RL -> 同 LR black(node) + red(g)
					rotateRight(parentNode);
					rotateLeft(grandNode);

					//setNodeRed(grandNode);
					setNodeBlack(node);
				} else {
					//RR -> red(grand)+ black(p)
					rotateLeft(grandNode);

					setNodeBlack(parentNode);
				}
			}
		} else {
			//3.parent.color == RED && uncle.color == RED (4)
			//red(grand) 并作为新节点添加到上面
			//black(parent) + black(uncle) 作为新的根节点
			setNodeBlack(parentNode);
			setNodeBlack(uncleNode);

			setNodeRed(grandNode);

			afterAdd(grandNode);
		}


	}

	@Override
	protected void afterRemove(TreeNode<E> node) {
		super.afterRemove(node);
	}

	/**
	 * 红黑树删除情况讨论：
	 * 1.删除的节点是 RED -> 不处理；
	 * 2.删除的节点是 BLACK ->
	 * -1-替换的节点 RED
	 * -2-
	 *
	 * @param node        删除的节点
	 * @param replacement 替换的节点
	 */
	@Override
	protected void afterRemove(TreeNode<E> node, TreeNode<E> replacement) {
		RedBlackNode<E> parentNode = getParentNode(node);
		//1.删除根节点 or 删除节点为红色
		if (parentNode == null || isNodeRed(node)) {
			return;
		}
		//2.replacement is red(此时对于 BST 而言，是度为1)
		if (isNodeRed(replacement)) {
			//将 replacement 染黑 即可
			setNodeBlack(replacement);
			return;
		}
		//3.删除的根节点为 Black && 替代节点为 Black(叶子节点 && 度为 2)
		RedBlackNode<E> siblingNode = getSiblingNode(node);
		if (isNodeBlack(siblingNode)) {
			//3.1 兄弟节点为黑色(作为主节点)
			RedBlackNode<E> leftSibling = (RedBlackNode<E>) siblingNode.left;
			RedBlackNode<E> rightSibling = (RedBlackNode<E>) siblingNode.right;
			//3.1.1. 不可借，发生下溢
			if (isNodeBlack(leftSibling) && isNodeBlack(rightSibling)) {
				afterRemove(parentNode, null);
				//最后再染色，因为删除的节点的颜色属性需要拿到新的一轮进行判断
				setNodeBlack(parentNode);
				setNodeRed(siblingNode);
				return;
			}
			if (siblingNode.isLeftChild()) {
				//L
				if (isNodeRed(leftSibling)) {
					//LL
					rotateRight(parentNode);

					setNodeBlack(leftSibling);
				} else {
					//LR - 说明 rightSibling is red
					rotateLeft(siblingNode);
					rotateRight(parentNode);

					setNodeBlack(rightSibling);
				}

			} else {
				//R
				if (isNodeRed(rightSibling)) {
					//RR
					rotateLeft(parentNode);

					setNodeBlack(rightSibling);
				} else {
					//RL
					rotateRight(siblingNode);
					rotateLeft(parentNode);

					setNodeBlack(leftSibling);
				}

			}
		} else {
			//3.2 兄弟节点为红色
			if (siblingNode.isLeftChild()) {
				//sibling is left node
				rotateRight(siblingNode);

			} else {
				//sibling is right node

				rotateLeft(siblingNode);
			}
			setNodeBlack(siblingNode);
			setNodeRed(parentNode);
			afterRemove(node, null);
		}
	}

	@Override
	protected TreeNode<E> createNode(E element, TreeNode<E> parent) {
		return new RedBlackNode<>(element, parent);
	}

	/**
	 * 打印 红黑树的节点
	 *
	 * @param node
	 * @return
	 */
	@Override
	public Object string(Object node) {
		RedBlackNode<E> myNode = (RedBlackNode<E>) node;
		String parentString = "null";
		if (myNode.parent != null) {
			parentString = myNode.parent.element.toString();
		}
		return myNode.element + "_p(" + parentString + ")" + "_(" + ((myNode.color.equals(RedBlackNode.Color.Red)) ? "红" : "黑") + ")";
	}

	//region	private methods

	/**
	 * 将节点染成红色
	 *
	 * @param node
	 */
	private void setNodeRed(TreeNode<E> node) {
		((RedBlackNode<E>) node).red();
	}

	/**
	 * 将节点染成黑色
	 *
	 * @param node
	 */
	private void setNodeBlack(TreeNode<E> node) {
		((RedBlackNode<E>) node).black();
	}

	/**
	 * 判断节点是否为黑色
	 * 在 node 的方法上多了一层 null 判断
	 *
	 * @param node
	 */
	private boolean isNodeBlack(TreeNode<E> node) {
		return node == null || ((RedBlackNode<E>) node).isBlack();
	}

	/**
	 * 判断节点是否为红色
	 *
	 * @param node
	 * @return
	 */
	private boolean isNodeRed(TreeNode<E> node) {
		return !isNodeBlack(node);
	}


	/**
	 * 获取父节点
	 *
	 * @param node
	 * @return
	 */
	private RedBlackNode<E> getParentNode(TreeNode<E> node) {
		return (RedBlackNode<E>) node.parent;
	}

	//endregion

	//region	protected methods

	@Override
	protected RedBlackNode<E> getUncleNode(TreeNode<E> node) {
		return (RedBlackNode<E>) super.getUncleNode(node);
	}

	/**
	 * 实现 自平衡接口
	 *
	 * @param prev
	 * @param grand
	 * @param parent
	 * @param child
	 */
	@Override
	public void afterRotate(TreeNode<E> prev, TreeNode<E> grand, TreeNode<E> parent, TreeNode<E> child) {
		if (prev == null) {
			root = parent;
			setNodeBlack(root);
		}
	}


	/**
	 * 由于节点已经删除，所以获取 兄弟节点其实跟正常情况不一样
	 * 只能从 红黑树删除的情况进行考虑
	 *
	 * @param node
	 * @return
	 */
	@Override
	protected RedBlackNode<E> getSiblingNode(TreeNode<E> node) {
		//对于红黑树删除情况，子节点为 null 时即为删除的节点
		TreeNode<E> parent = node.parent;
		if (parent==null){
			return null;
		}
		if (parent.left == null) {
			return (RedBlackNode<E>)parent.right;
		}else {
			return (RedBlackNode<E>)parent.left;
		}
	}

	//endregion
}
